package Midium;

import java.util.*;

public class Solution103 {
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        deque.add(root);
        int high = 1;
        while (!deque.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            while (!deque.isEmpty()) {
                if (high % 2 == 0)
                    queue.offer(deque.removeFirst());
                else
                    queue.offer(deque.removeLast());
            }
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                list.add(node.val);
                if (high % 2 == 0) {
                    // 先右后左
                    if (node.right != null) {
                        deque.addLast(node.right);
                    }
                    if (node.left != null) {
                        deque.addLast(node.left);
                    }
                } else {
                    if (node.left != null) {
                        deque.addFirst(node.left);
                    }
                    if (node.right != null) {
                        deque.addFirst(node.right);
                    }
                }
            }
            high++;
            ans.add(list);
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        zigzagLevelOrder(root);
    }
}
